堆積(Heap)建立的方法(以最大堆積實作)

• maxHeapify: 最大堆積化
• push: 新增元素
• pop: 刪除特定元素
• popRoot: 刪除根節點(最大值)
• getRoot: 查看根節點(最大值)
• printHeap: 印出最大堆積

堆積的介紹可以參考此篇。

JavaScript

//MaxHeap
class MaxHeap{
  constructor(){
    this.list = [];
  }
  
  //最大堆積化
  maxHeapify = (arr, n, i) => {
    let largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;
     if (l < n && arr[l] > arr[largest]) {
           largest = l; 
     }
     if (r < n && arr[r] > arr[largest]) {
          largest = r; 
     }
     if (largest != i) { 
        [arr[i],arr[largest]] = [arr[largest],arr[i]];
        this.maxHeapify(arr, n, largest); 
      } 
  }
  
  //新增元素
  push = (num) => {
    const size = this.list.length;
    if(size === 0){
      this.list.push(num);
    }else{
      this.list.push(num);
      for (let i = parseInt(this.list.length / 2 - 1); i >= 0; i--) {
         this.maxHeapify(this.list, this.list.length, i); 
      }
    }
  }
  
  //刪除元素
  pop = (num) => {
    const size = this.list.length;
    
    let i;
    for(i = 0; i < size; i++){
      if(num === this.list[i]){
        break;
      }
    }
    
    //要刪除元素與最後一個元素交換
    [this.list[i], this.list[size - 1]] = [this.list[size - 1], this.list[i]];
    
    //刪除最後一個元素
    this.list.splice(size - 1);
    
    for (let i = parseInt(this.list.length / 2 - 1); i >= 0; i--) {
         this.maxHeapify(this.list, this.list.length, i); 
     }
  }
  
  //回傳最大值
  getRoot = () => this.list[0];
  
  //刪除最大值
  popRoot = () => {
    this.pop(this.list[0]);
  }
  
  //印出最大堆積
  printHeap = () => this.list;
}

let heap = new MaxHeap()
heap.push(20)
heap.push(10)
heap.push(5)
heap.push(80)
heap.push(75)
heap.push(78)
heap.push(72)
heap.push(73)
console.log(heap.printHeap())//80, 75, 78, 73, 20, 5, 72, 10
heap.popRoot()
console.log(heap.printHeap())//78, 75, 72, 73, 20, 5, 10

Python

heapq是能實現Heap結構的套件，Python滿多會使用此種作法，只不過在刪除元素時，似乎只有把最小/大值刪除的方法，這應該是因為用Heap來達到優先佇列(Priority Queue)的需求，權重最高的根節點會優先處理，後進先出的概念。

#MaxHeap
import heapq
class MaxHeap:
    def __init__(self):
        self.maxheap = []

    def push(self, key):
        heapq.heappush(self.maxheap, key)
        heapq._heapify_max(self.maxheap)

    def getRoot(self):
        return self.maxheap[0]

    def popRoot(self):
        heapq.heappop(self.maxheap)
        heapq._heapify_max(self.maxheap)

    def printHeap(self):
        print(self.maxheap)

heap = MaxHeap()
heap.push(20)
heap.push(10)
heap.push(5)
heap.push(80)
heap.push(75)
heap.push(78)
heap.push(72)
heap.push(73)
heap.printHeap()#80, 75, 78, 73, 20, 5, 72, 10
heap.popRoot()
heap.printHeap()#78, 75, 72, 73, 20, 5, 10
heap.popRoot()
heap.printHeap()#75, 73, 10, 72, 20, 5

佇列的介紹可以參考此篇。